|
The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems. The problem models the following real-life problem: :There are a set of ''n'' facilities and a set of ''n'' locations. For each pair of locations, a ''distance'' is specified and for each pair of facilities a ''weight'' or ''flow'' is specified (e.g., the amount of supplies transported between the two facilities). The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows. Intuitively, the cost function encourages factories with high flows between each other to be placed close together. The problem statement resembles that of the assignment problem, except that the cost function is expressed in terms of quadratic inequalities, hence the name. ==Formal mathematical definition== The formal definition of the quadratic assignment problem is as follows: :Given two sets, ''P'' ("facilities") and ''L'' ("locations"), of equal size, together with a weight function ''w'' : ''P'' × ''P'' → R and a distance function ''d'' : ''L'' × ''L'' → R. Find the bijection ''f'' : ''P'' → ''L'' ("assignment") such that the cost function: :: :is minimized. Usually weight and distance functions are viewed as square real-valued matrices, so that the cost function is written down as: : In matrix notation: : where are the permutation matrices, "W" is the weight matrix and "D" is the distance matrix. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Quadratic assignment problem」の詳細全文を読む スポンサード リンク
|